package com.lwx.test;

import java.util.Arrays;

public class LCP23 {
    public static void main(String[] args) {
//        int[] arr = {2,4,3,1,5};
        int[] arr = {5,4,3,2,1};
        System.out.println(isMagic(arr));
    }
    public static boolean isMagic(int[] target) {
        int[] origin = new int[target.length];
        for (int i = 0; i < target.length; i++) {
            origin[i] = i+1;
        }
        int[] tmp1 =  OddBeforeEven(origin);
        int k = getK(target, tmp1);
        return OddBeforeEvenAndCompare(target,origin,0,k);
    }

    public static int[] OddBeforeEven(int[] arr){
        int[] tmp = new int[arr.length];
        int j = 0;
        for (int i = 1; i <arr.length ; i +=2) {
            tmp[j++] = arr[i];
        }
        for (int i = 0; i < arr.length; i+=2) {
            tmp[j++] = arr[i];
        }
        return tmp;
    }

    //arr[l...n]偶数放在奇数前面，且比较从l开始的前k位(l,l+k)两个数组target和arr是否相等
    public static boolean OddBeforeEvenAndCompare(int[] target,int[] arr, int l,int k){
        if(k == 0){
            return false;
        }
        int[] tmp = new int[arr.length];
        for (int i = l+1; i <arr.length ; i +=2) {
           tmp[l++] = arr[i];
        }
        for (int i = l; i < arr.length; i+=2) {
            tmp[l++] = arr[i];
        }
        //此时将剩下的牌进行全部比较
        if(arr.length-l < k){
            for (int i = l; i <arr.length ; i++) {
                if(arr[i] != target[i]){
                    return false;
                }
            }
            return true;
        }else {
            for (int i = l; i < l+k; i++) {
                if(tmp[i] != target[i]){
                    return false;
                }
            }
            return OddBeforeEvenAndCompare(target,tmp,l+k,k);
        }

    }

    public static int getK(int[] origin, int[]target){
        int k = 0;
        for (int i = 0; i < origin.length; i++) {
            if(origin[i] == target[i]){
                k++;
            }else {
                return k;
            }
        }
        return k;
    }
}
